/*
 * jxUtils Project (2013, 2014)
 * 
 * by Denilson Edinaldo Pinto
 * 
 * LGPL
 * Copyright (C) 2014
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program. If not, see <http://www.gnu.org/licenses/>.
 */
package org.jxUtils.collection;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import org.jxUtils.check.CheckUtil;
import org.jxUtils.lang.StringUtil;

/**
 * Esta classe implementa métodos de Ordenação para Coleções.
 * 
 * @author Denilson Edinaldo Pinto
 * @project jxUtils
 * @package org.jxUtils.collection
 * @date 06/02/2013 - 22:03:25
 */
public class SortUtil {
	
	/**
	 * Ordena o <b>array</b> utilizando o algoritmo de ordenação <b>BubbleSort</b>
	 * 
	 * @param array
	 */
	public final static <E extends Comparable<? super E>> void bubbleSort(final E[] array) {
	
		//
		if(CheckUtil.isNotNull(array)) {
			
			E aux;

			// 
			for(int i = array.length; i >= 1; i--) {

				// 
				for(int j = 1; j < i; j++) {

					// 
					if(array[j - 1].compareTo(array[j]) > 0) {
						
						aux = array[j];
						
						array[j] = array[j - 1];
						
						array[j - 1] = aux;
					}
				}
			}
		}
	}
	
	/**
	 * Ordena o <b>arry</b> utilizando o algoritmo de ordenação <b>CockTail</b>
	 * 
	 * @param array
	 */
	public final static <E extends Comparable<? super E>> void cocktail(final E[] array) {
	
		//
		if(CheckUtil.isNotNull(array)) {
			
			E aux;
			
			final int tamanho = 19; // para um vetor de 20 elementos
			int inicio = 0;
			int fim = tamanho - 1;
			int swap = 0;

			// 
			while(swap == 0 && inicio < fim) {
				
				swap = 1;

				// 
				for(int i = inicio; i < fim; i = i + 1) {

					// 
					if(array[i].compareTo(array[i + 1]) > 0) {
						
						aux = array[i];
						
						array[i] = array[i + 1];
						
						array[i + 1] = aux;
						
						swap = 0;
					}
				}
				
				fim = fim - 1;

				// 
				for(int i = fim; i > inicio; i = i - 1) {

					// 
					if(array[i].compareTo(array[i - 1]) < 0) {
						
						aux = array[i];
						
						array[i] = array[i - 1];
						
						array[i - 1] = aux;
						
						swap = 0;
					}
				}
				
				inicio = inicio + 1;
			}
		}
	}
	
	/**
	 * Ordena o <b>array</b> utilizando o algoritmo de ordenação <b>CombSort</b>
	 * 
	 * @param array
	 */
	public final static <E extends Comparable<? super E>> void combSort(final E[] array) {
	
		//
		if(CheckUtil.isNotNull(array)) {
			
			int gap = array.length;
			
			boolean swapped = true;

			// 
			while(gap > 1 || swapped) {

				// 
				if(gap > 1) {
					
					gap = (int)(gap / 1.247330950103979);
				}
				
				int i = 0;
				
				swapped = false;

				// 
				while(i + gap < array.length) {

					// 
					if(array[i].compareTo(array[i + gap]) > 0) {
						
						final E temp = array[i];
						
						array[i] = array[i + gap];
						
						array[i + gap] = temp;
						
						swapped = true;
					}
					
					i++;
				}
			}
		}
	}
	
	/**
	 * Ordena o <b>array</b> utilizando o algoritmo de ordenação <b>GnomeSort</b>
	 * 
	 * @param array
	 */
	public final static <E extends Comparable<? super E>> void gnomeSort(final E[] array) {
	
		//
		if(CheckUtil.isNotNull(array)) {
			
			int i = 1;
			
			E temp = null;

			// 
			while(i < array.length) {

				// 
				if(i == 0 || array[i - 1].compareTo(array[i]) <= 0) {
					
					i++;
					
				}else {
					
					temp = array[i - 1];
					
					array[i - 1] = array[i];
					
					array[i] = temp;
					
					i--;
				}
			}
		}
	}
	
	/**
	 * Ordena o <b>array</b> utilizando o algoritmo de ordenação <b>HeapSort</b>
	 * 
	 * @param array
	 */
	public final static <E extends Comparable<? super E>> void heapSort(final E[] array) {
	
		//
		if(CheckUtil.isNotNull(array)) {
			
			HeapSort.sort(array);
		}
	}
	
	/**
	 * Ordena o <b>array</b> utilizando o algoritmo de ordenação <b>InsertionSort</b>
	 * 
	 * @param array
	 */
	public final static <E extends Comparable<? super E>> void insertionSort(final E[] array) {
	
		//
		if(CheckUtil.isNotNull(array)) {

			// 
			for(int i = 1; i < array.length; i++) {
				
				final E element = array[i];

				// 
				for(int j = i - 1; j >= 0 && array[j].compareTo(element) > 0; j--) {
					
					array[j + 1] = array[j];
					
					array[j] = element;
				}
			}
		}
	}
	
	/**
	 * Ordena o <b>array</b> utilizando o algoritmo de ordenação <b>MergeSort</b>
	 * 
	 * @param array
	 */
	public final static <E extends Comparable<? super E>> void mergeSort(final E[] array) {
	
		MergeSort.sort(array);
	}
	
	/**
	 * Ordena o <b>array</b> utilizando o algoritmo de ordenação <b>QuickSort</b>
	 * 
	 * @param array
	 */
	public final static <E extends Comparable<? super E>> void quickSort(final E[] array) {
	
		QuickSort.sort(array);
	}
	
	/**
	 * Ordena o <b>array</b> utilizando o algoritmo de ordenação <b>SelectionSort</b>
	 * 
	 * @param array
	 */
	public final static <E extends Comparable<? super E>> void selectionSort(final E[] array) {
	
		//
		if(CheckUtil.isNotNull(array)) {
			
			int index_min;
			
			E aux;

			// 
			for(int i = 0; i < array.length; i++) {
				
				index_min = i;

				// 
				for(int j = i + 1; j < array.length; j++) {

					// 
					if(array[j].compareTo(array[index_min]) < 0) {
						
						index_min = j;
					}
				}

				// 
				if(index_min != i) {
					
					aux = array[index_min];
					
					array[index_min] = array[i];
					
					array[i] = aux;
				}
			}
		}
	}
	
	/**
	 * Ordena o <b>array</b> utilizando o algoritmo de ordenação <b>ShellSort</b>
	 * 
	 * @param array
	 */
	public final static <E extends Comparable<? super E>> void shellSort(final E[] array) {
	
		//
		if(CheckUtil.isNotNull(array)) {
			
			E aux;
			
			final int n = array.length;
			int h = n / 2;
			int j;

			// 
			while(h > 0) {

				// 
				for(int i = h; i < n; i++) {
					
					aux = array[i];
					j = i;

					// 
					while(j >= h && array[j - h].compareTo(aux) > 0) {
						
						array[j] = array[j - h];
						
						j = j - h;
					}
					
					array[j] = aux;
				}
				
				h = h / 2;
			}
		}
	}
	
	/**
	 * @param array
	 */
	public final static void sort(final Object[] array) {
	
		//
		if(CheckUtil.isNotNull(array)) {
			
			Object aux;

			// 
			for(int i = array.length; i >= 1; i--) {

				// 
				for(int j = 1; j < i; j++) {

					// 
					if(StringUtil.normalize(array[j - 1].toString()).compareTo(StringUtil.normalize(array[j].toString())) > 0) {
						
						aux = array[j];
						
						array[j] = array[j - 1];
						
						array[j - 1] = aux;
					}
				}
			}
		}
	}
	
	/**
	 * @author Denilson Edinaldo Pinto
	 * @project jxUtils
	 * @package org.jxUtils.collection
	 */
	private static class HeapSort {
		
		/**
		 * @param array
		 */
		private static <T extends Comparable<? super T>> void buildMaxHeap(final T[] array) {

			// 
			for(int index = array.length / 2 - 1; index >= 0; index--) {
				
				maxHeapify(array, index, array.length);
			}
		}
		
		/**
		 * @param array
		 * @param pos
		 * @param n
		 */
		private static <T extends Comparable<? super T>> void maxHeapify(final T[] array, final int pos, final int n) {
		
			int max = 2 * pos + 1;
			final int right = max + 1;
			
			//
			if(max < n) {

				// 
				if(right < n && array[max].compareTo(array[right]) < 0) {
					
					max = right;
				}

				// 
				if(array[max].compareTo(array[pos]) > 0) {
					
					swap(array, max, pos);
					
					maxHeapify(array, max, n);
				}
			}
		}
		
		/**
		 * @param array
		 */
		public static <T extends Comparable<? super T>> void sort(final T[] array) {
		
			buildMaxHeap(array);
			
			int n = array.length;

			// 
			for(int i = array.length - 1; i > 0; i--) {
				
				swap(array, i, 0);
				
				maxHeapify(array, 0, --n);
			}
		}
		
		/**
		 * @param v
		 * @param j
		 * @param aposJ
		 */
		public static void swap(final Object[] v, final int j, final int aposJ) {
		
			final Object aux = v[j];
			
			v[j] = v[aposJ];
			
			v[aposJ] = aux;
		}
	}
	
	/**
	 * @author Denilson Edinaldo Pinto
	 * @project jxUtils
	 * @package org.jxUtils.collection
	 */
	private static class MergeSort {
		
		/**
		 * @param p
		 * @param q
		 * @param r
		 * @param array
		 */
		private static <E extends Comparable<? super E>> void merge(final int p, final int q, final int r, final E[] array) {
		
			int i = p;
			int j = q;
			int k = 0;
			
			final List<E> aux = new ArrayList<E>();

			// 
			while(i < q && j < r) {

				// 
				if(array[i].compareTo(array[j]) <= 0) {
					
					aux.add(k++, array[i++]);
					
				}else {
					
					aux.add(k++, array[j++]);
				}
			}

			// 
			while(i < q) {
				
				aux.add(k++, array[i++]);
			}

			// 
			while(j < r) {
				
				aux.add(k++, array[j++]);
			}

			// 
			for(i = p; i < r; ++i) {
				
				array[i] = aux.get(i - p);
			}
		}
		
		/**
		 * @param n
		 * @param array
		 */
		private static <E extends Comparable<? super E>> void mergeSort(final int n, final E[] array) {
		
			int p;
			int r;
			int b = 1;

			// 
			while(b < n) {
				
				p = 0;

				// 
				while(p + b < n) {
					
					r = p + 2 * b;
					
					if(r > n) {
						
						r = n;
					}
					
					merge(p, p + b, r, array);
					
					p = p + 2 * b;
				}
				
				b = 2 * b;
			}
		}
		
		/**
		 * @param array
		 */
		public static <E extends Comparable<? super E>> void sort(final E[] array) {
		
			//
			if(CheckUtil.isNotNull(array)) {
				
				mergeSort(array.length, array);
			}
		}
	}
	
	/**
	 * @author Denilson Edinaldo Pinto
	 * @project jxUtils
	 * @package org.jxUtils.collection
	 */
	private static class QuickSort {
		
		private final static Random RND = new Random();
		
		/**
		 * @param array
		 * @param begin
		 * @param end
		 */
		private static <E extends Comparable<? super E>> int partition(final E[] array, final int begin, final int end) {
		
			int index = begin + RND.nextInt(end - begin + 1);
			
			final E pivot = array[index];
			
			swap(array, index, end);

			// 
			for(int i = index = begin; i < end; ++i) {

				// 
				if(array[i].compareTo(pivot) <= 0) {
					
					swap(array, index++, i);
				}
			}
			
			swap(array, index, end);
			
			return index;
		}
		
		/**
		 * @param array
		 * @param begin
		 * @param end
		 */
		private static <E extends Comparable<? super E>> void qsort(final E[] array, final int begin, final int end) {
		
			//
			if(end > begin) {
				
				final int index = partition(array, begin, end);
				
				qsort(array, begin, index - 1);
				
				qsort(array, index + 1, end);
			}
		}
		
		/**
		 * @param array
		 * @param i
		 * @param j
		 */
		private static void swap(final Object[] array, final int i, final int j) {
		
			final Object tmp = array[i];
			
			array[i] = array[j];
			
			array[j] = tmp;
		}
		
		/**
		 * @param array
		 */
		public static <E extends Comparable<? super E>> void sort(final E[] array) {
		
			//
			if(CheckUtil.isNotNull(array)) {
				
				qsort(array, 0, array.length - 1);
			}
		}
	}
}
